CC4 Lec 4

Question 1

A stack is also known as a ___ list

Answer 1

Last-In-First-Out (LIFO)

Question 2

(T) A stack is a linear structure in which items are added or removed only at one end the top.​

Question 3

(T) The depth of stack is the number of elements it contains.

Question 4

(T) An empty stack has depth zero.

Question 5

(T) Elements are ordered​

Question 6

(T) Stack user cannot have direct access to data items inside the stack​

Question 7

(T) Only topmost item can be retrieved​

Question 8

(T) Can hold any number of data items (in principle), however, there is an upper limit to stack size depending on the memory space​

Question 9

A list with the restriction that insertion and deletion can be performed only from one end, called the top.

Answer 9

​STACK ADT (Abstract Data Type)

Question 10

Insert or push some item “x” onto the stack.​

Answer 10

Push (x)

Question 11

Before this operation, the stack if often checked if it has enough ______ to accommodate the new item​

If stack is full, an _____would occur​

Answer 11

capacity, overflow

Question 12

Removing the most recent item or element from the stack.​

Answer 12

Pop( )

Question 13

Must ensure that the stack is not ___ before this operation​

If stack contains no item, popping would cause an ____ error​

Answer 13

empty, underflow

Question 14

Returns the copy of the item or element at the TOP of the stack.​

Answer 14

TOP

Question 15

This operation is also called PEEK​

Answer 15

TOP

Question 16

It will return true if the stack is EMPTY, false otherwise.​

Answer 16

IsEmpty( )

Question 17

It will return true if the stack is FULL, false otherwise.​

Answer 17

IsFull()

Question 18

GENERATES an empty stack object and reserves necessary storage space​

Answer 18

Create

Question 19

REMOVES all elements from the stack and releases memory allocated to stack​

Answer 19

Destroy

Question 20

(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.​

​

Question 21

(T) Method pop removes the tail element. In this case, the cost for each push or pop operation is only Θ(1).​

Question 22

(T) as elements are pushed onto the stack, they are appended to the tail of the list.​

Question 23

(T) When an element is popped off, top is decremented by 1

Question 24

(T) When an element is pushed onto stack, top is incremented by 1​

Question 25

(T) The elements of stack are placed in a sequential order in the array​

Question 26

(T) Size of array determines the maximum number of data elements in the stack​

Question 27

(T) Elements are inserted and removed only from the head of the list. ​

Question 28

(T)
A header node is not used because no special-case code is required for lists of zero or one elements.​

Question 29

(T) The only data member is top, a pointer to the first (top) link node of the stack.

Question 30

(T) Method push first modifies the next field of the newly created link node to point to the top of the stack and then sets top to point to the new link node.​

Question 31

(T) Method pop is also quite simple. Variable temp stores the top nodes’ value, while l temp links to the top node as it is removed from the stack.

Question 32

(T) The stack is updated by setting top to point to the next link in the stack. ​

Question 33

(T) The old top node is then returned to free store (or the free list), and the element value is returned​

Question 34

3 types

Answer 34

Push, Pop, Top

Question 35

Array implementation: Stack

Answer 35

Simplified version of the array based list