Stacks Flashcards
What is a stack implementation?
it is like a container that stores a collection of elements, they adopt a LIFO last in first out method of accessing the elements.
what are supported operations that can be done with stack?
return the size, determine if its empty, empty the stack
what are operations that you cant do with stack?
search the stack for a specific element, remove specific element, deal with specific elements.
what does push() do
stores an element at the top of the stack pointed to by parameter stack
what does pop() do
removes the elements at the top of the stack, returns true when complete of false if the stack is empty
what does peek() do
retrieves the element from the top of the stack and returns true as long as the stack is not empty when peek is called
what is the computational time for a stack?
size() O(1)
check_empty() O(1)
empty() O(n)
peek() O(1)
push(data) O(1)
pop() O(1)
what are some applications of stack implementation?
◼ Page-visited history in a Web browser
◼ Undo sequence in a text editor
◼ Chain of method calls in the Java Virtual Machine
What is a stack?
A stack is a collection of elements that maintains the order in which they were added, following the last-in, first-out (LIFO) principle
What are the fundamental operations provided by stacks?
The fundamental operations provided by stacks include push (add an element to the top of the stack), pop (remove and return the top element from the stack), and peek (return the top element without removing it)
How can you implement a stack using a linked list?
You can implement a stack using a linked list by treating the head node of the linked list as the top of the stack and performing push and pop operations by inserting and removing nodes at the head of the list, respectively.
What additional operations are typically not provided by stack implementations?
Additional operations typically not provided by stack implementations include searching for a specific element, removing a specific element, and accessing elements at specific positions in the stack, as these operations contradict the stack’s LIFO protocol
How can you determine if a stack is empty?
You can determine if a stack is empty by checking if the size of the stack is 0.
What is the computational time complexity of common stack operations?
Common stack operations such as push, pop, and peek typically have a computational time complexity of O(1), meaning their execution time does not depend on the size of the stack
What are some applications of stacks in computing?
Some applications of stacks in computing include maintaining page-visited history in web browsers, implementing an undo sequence in text editors, and managing the chain of method calls in the Java Virtual Machine.
