CC4 Lec 4 Flashcards

1
Q

A stack is also known as a ___ list

A

Last-In-First-Out (LIFO)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

(T) An empty stack has depth zero.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

(T) Elements are ordered​

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

(T) Only topmost item can be retrieved​

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

(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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

​STACK ADT (Abstract Data Type)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

Push (x)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

If stack is full, an _____would occur​

A

capacity, overflow

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

Pop( )

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

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

A

empty, underflow

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

TOP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

This operation is also called PEEK​

A

TOP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

IsEmpty( )

17
Q

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

A

IsFull()

18
Q

GENERATES an empty stack object and reserves necessary storage space​

A

Create

19
Q

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

A

Destroy

20
Q

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

A
21
Q

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

A
22
Q

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

A
23
Q

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

A
24
Q

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

A
25
Q

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

A
26
Q

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

A
27
Q

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

A
28
Q

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

A
29
Q

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

A
30
Q

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

A
31
Q

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

A
32
Q

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

A
33
Q

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

A
34
Q

3 types

A

Push, Pop, Top

35
Q

Array implementation: Stack

A

Simplified version of the array based list