Stack and Queue - Part 1: Stack

Flashcards about Stacks, covering definition, operations, exceptions, applications, implementation and use cases.

What is a Stack?

A linear data structure that can be accessed only at one of its ends for storing and retrieving data, following the Last In, First Out (LIFO) principle.

What are the common operations performed on a stack?

clear(), isEmpty(), push(el), pop(), top()

What is a Stack Exception?

An error condition that occurs when an operation of ADT cannot be executed, such as attempting to pop or top on an empty stack.

What are some common applications of stacks?

Parentheses nesting, evaluating arithmetic expressions, implementing function calls, backtracking, undo sequence in a text editor, auxiliary data structure for algorithms.

How does a Stack in computer memory actually work?

Each time a method is called, an activation record (AR) is allocated for it, containing parameters, local variables, a dynamic link, return address, and return value.

What is an Array-based Stack?

A simple way of implementing the Stack ADT using an array, with a variable 'top' keeping track of the index of the top element.

What happen if the array storing the stack elements may become full in Array-based Stack?

A push operation will throw a FullStackException

How is a stack implemented using a Linked List?

Implemented using nodes with references to the next node in the stack. The 'head' pointer indicates the top of the stack.

How can a stack be implemented using ArrayList & LinkedList classes in Java?

By using ArrayList or LinkedList classes. Both classes provide methods to implement stack operations such as push and pop.

How is a stack used to convert a decimal integer number to binary?

Used to convert a decimal integer number to binary by pushing remainders onto the stack and then popping them off to form the binary representation.

How is a stack used to validate expressions?

Used to validate that each opening symbol (parentheses, braces, brackets) matches its corresponding closing symbol in the correct order.

How does Matching Parentheses relate to Matching HTML Tags

Can use stack to check whether an HTML document is valid or not by check matching tags.

What is the Stack class in Java

A Stack class implemented in the java.util package is an extension of class Vector to which one constructor and five methods are added.

Summary of Stack usage

Stack is a linear data structure that can be accessed at only one of its ends for storing and retrieving data and called a Last In, First Out (LIFO) structure.

A linear data structure that can be accessed only at one of its ends for storing and retrieving data, following the Last In, First Out (LIFO) principle.

What is a Stack?

clear(), isEmpty(), push(el), pop(), top()

What are the common operations performed on a stack?

An error condition that occurs when an operation of ADT cannot be executed, such as attempting to pop or top on an empty stack.

What is a Stack Exception?

Parentheses nesting, evaluating arithmetic expressions, implementing function calls, backtracking, undo sequence in a text editor, auxiliary data structure for algorithms.

What are some common applications of stacks?

Each time a method is called, an activation record (AR) is allocated for it, containing parameters, local variables, a dynamic link, return address, and return value.

How does a Stack in computer memory actually work?

A simple way of implementing the Stack ADT using an array, with a variable 'top' keeping track of the index of the top element.

What is an Array-based Stack?

A push operation will throw a FullStackException

What happen if the array storing the stack elements may become full in Array-based Stack?

Implemented using nodes with references to the next node in the stack. The 'head' pointer indicates the top of the stack.

How is a stack implemented using a Linked List?

By using ArrayList or LinkedList classes. Both classes provide methods to implement stack operations such as push and pop.

How can a stack be implemented using ArrayList & LinkedList classes in Java?

Used to convert a decimal integer number to binary by pushing remainders onto the stack and then popping them off to form the binary representation.

How is a stack used to convert a decimal integer number to binary?

Used to validate that each opening symbol (parentheses, braces, brackets) matches its corresponding closing symbol in the correct order.

How is a stack used to validate expressions?

Can use stack to check whether an HTML document is valid or not by check matching tags.

How does Matching Parentheses relate to Matching HTML Tags

A Stack class implemented in the java.util package is an extension of class Vector to which one constructor and five methods are added.

What is the Stack class in Java

Stack is a linear data structure that can be accessed at only one of its ends for storing and retrieving data and called a Last In, First Out (LIFO) structure.

Summary of Stack usage

The time complexity of both push and pop operations is $O(1)$, as they only involve accessing the top element of the array.

What is the time complexity of push and pop operations in a stack implemented using an array?

The space complexity is $O(n)$, where n is the maximum number of elements that can be stored in the stack.

What is the space complexity of a stack implemented using an array?

The time complexity of both push and pop operations is $O(1)$, as they only involve adding or removing the head node of the linked list.

What is the time complexity of push and pop operations in a stack implemented using a linked list?

The space complexity is $O(n)$, where n is the number of elements in the stack. Each element requires a node in the linked list.

What is the space complexity of a stack implemented using a linked list?

Dynamic size (can grow or shrink as needed), no risk of FullStackException.

What are the advantages of using a linked list over an array for implementing a stack?

Better memory locality, potentially faster access, simpler implementation.

What are the advantages of using an array over a linked list for implementing a stack?