CC4 Lec 4 Flashcards
A stack is also known as a ___ list
Last-In-First-Out (LIFO)
(T) A stack is a linear structure in which items are added or removed only at one end the top.
(T) The depth of stack is the number of elements it contains.
(T) An empty stack has depth zero.
(T) Elements are ordered
(T) Stack user cannot have direct access to data items inside the stack
(T) Only topmost item can be retrieved
(T) Can hold any number of data items (in principle), however, there is an upper limit to stack size depending on the memory space
A list with the restriction that insertion and deletion can be performed only from one end, called the top.
STACK ADT (Abstract Data Type)
Insert or push some item “x” onto the stack.
Push (x)
Before this operation, the stack if often checked if it has enough ______ to accommodate the new item
If stack is full, an _____would occur
capacity, overflow
Removing the most recent item or element from the stack.
Pop( )
Must ensure that the stack is not ___ before this operation
If stack contains no item, popping would cause an ____ error
empty, underflow
Returns the copy of the item or element at the TOP of the stack.
TOP
This operation is also called PEEK
TOP
It will return true if the stack is EMPTY, false otherwise.
IsEmpty( )
It will return true if the stack is FULL, false otherwise.
IsFull()
GENERATES an empty stack object and reserves necessary storage space
Create
REMOVES all elements from the stack and releases memory allocated to stack
Destroy
(T) Inefficient implementation because now every push or pop operation will require that all elements currently in the stack be shifted one position in the array, for a cost of Θ(n) if there are n elements.
(T) Method pop removes the tail element. In this case, the cost for each push or pop operation is only Θ(1).
(T) as elements are pushed onto the stack, they are appended to the tail of the list.
(T) When an element is popped off, top is decremented by 1
(T) When an element is pushed onto stack, top is incremented by 1
